package com.nowcoder.code.lcof;

import java.util.ArrayList;
import java.util.LinkedList;

public class JZ59RE {

    public static void main(String[] args) {

    }


    public ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> result = new ArrayList<>();
        if (num == null || num.length == 0 || size == 0 || size > num.length) {
            return result;
        }

        LinkedList<Integer> list = new LinkedList<>();


        for (int i = 0; i < size; i++) {
            while (!list.isEmpty() && num[i] > num[list.getLast()]) {
                list.removeLast();
            }
            list.add(i);
        }

        for (int i = size; i < num.length; i++) {
            result.add(num[list.getFirst()]);

            while (!list.isEmpty() && i - size >= list.getFirst()) {
                list.removeFirst();
            }

            while (!list.isEmpty() && num[i] > num[list.getLast()]) {
                list.removeLast();
            }
            list.add(i);
        }

        result.add(num[list.getFirst()]);

        return result;
    }

}
